<?php
/*
 * 给定数组arr和整数num，共返回有多少个子数组满足如下情况：
 * max(arr[i..j]) - min(arr[i..j]) <= num
 * max(arr[i..j])表示子数组arr[i..j]中的最大值，
 * min(arr[i..j])表示子数组arr[i..j]中的最小值。
 * 【要求】
 * 如果数组长度为N，请实现时间复杂度为O(N)的解法
 */

require_once '../../../class/DoubleEndedQueue.class.php';
$arr = [2, 5, 7, 7, 7, 1, 3, 7, 8, 4, 6, 6, 3, 2, 6, 2, 7, 1, 4, 0, 7, 7, 9, 3, 5, 9, 5, 6, 7, 5,];
$num = 5;
$obj = new Code_05_AllLessNumSubArray();
echo $obj->do($arr, $num);

class Code_05_AllLessNumSubArray
{
    // 思路类似 【初级->Day08->Code_05_生成窗口最大值数组】题目，维护两个双端队列
    public function do($arr, $num)
    {
        $len = count($arr);
        if ($arr == null || $len == 0) {
            return 0;
        }
        $qmin = new DoubleEndedQueue();
        $qmax = new DoubleEndedQueue();
		$i = 0;
		$j = 0;
		$res = 0;
        while ($i < $len) {
            while ($j < $len) {
                while (!$qmin->isEmpty() && $arr[$qmin->getLast()] >= $arr[$j]) {
                    $qmin->removeLast();
                }
                $qmin->addLast($j);
                while (!$qmax->isEmpty() && $arr[$qmax->getLength()] <= $arr[$j]) {
                    $qmax->removeLast();
                }
                $qmax->addLast($j);
                if ($arr[$qmax->getFirst()] - $arr[$qmin->getFirst()] > $num) {
                    break;
                }
                $j++;
            }
            if ($qmin->getFirst() == $i) {
                $qmin->removeFirst();
            }
            if ($qmax->getFirst() == $i) {
                $qmax->removeFirst();
            }
            $res += $j - $i;
            $i++;
        }
        return $res;
	}

}